package com.lfg.leetcode.leetcode0;


public class No45Jump {

    public static void main(String[] args) {
        int ret = jump(new int[]{4, 1, 1, 3, 1, 1, 1});
        System.out.println(ret);
    }

    public static int jump(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return 0;
        }
        int[] cnt = new int[length];
        int index = length;
        int max = 0;
        for (int i = 0; i < length; i++) {
            if (i > index) {
                cnt[i] = max;
                continue;
            }
            int num = i + nums[i];
            if (i > 0 && (cnt[i] == 0 || cnt[i] > cnt[i - 1])) {
                cnt[i] = cnt[i - 1] + 1;
            }
            if (i == 0) {
                cnt[i] = 1;
            }
            if (num < length && (cnt[num] == 0 || cnt[num] > cnt[i])) {
                cnt[num] = cnt[i] + 1;
            }
            if (num >= length - 1) {
                index = i;
                max = cnt[i];
            }
        }
        return cnt[length - 1];
    }
}

